// https://www.lintcode.com/problem/remove-duplicate-numbers-in-array/description

class Solution {
public:
    /**
     * @param nums: an array of integers
     * @return: the number of unique integers
     */
     
    // 个：O(n) time, O(1) space
    // int deduplication(vector<int> &nums) {
    //     int t = 0;
    //     for (int i = 0; i < nums.size(); ++i)
    //     {
    //         if (find(nums.begin(), nums.end(), nums[t]) - nums.begin() < t)
    //         {
    //             int tmp = nums[t];
    //             nums[t] = nums[nums.size() - 1 - i + t];
    //             nums[nums.size() - i + t] = tmp;
    //             t--;
    //         }
    //         t++;
    //     }
    //     return t;
    // }
    
    // O(n) time, O(n) space:set或者map
    int deduplication(vector<int> &nums) {
        set<int> st(nums.begin(), nums.end());
        int i = 0;
        for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
        {
            nums[i++] = *it;
        }
        return st.size();
    }


    // O(nlogn) time, O(1) extra space
    // 建立一个指针，指针指向目前位置不同的数的末尾，如果当前元素与末尾不同，则加入到末尾
    // int deduplication(vector<int> &nums) {
    //     if (nums.empty())
    //     {
    //         return 0;
    //     }
    //     sort(nums.begin(), nums.end());
    //     int pos = 0;
    //     for (int i = 0; i < nums.size(); ++i)
    //     {
    //         if (nums[i] != nums[pos])
    //         {
    //             nums[++pos] = nums[i];
    //         }
    //     }
    //     return pos + 1;
    // }
};